The present invention relates to a technique on Viterbi decoding for decoding a trellis-coded modulated signal.
As a conventional configuration for decoding a trellis-coded modulated signal, a Viterbi decoder as shown in FIG. 13 has been proposed (Japanese Laid-Open Patent Publication No. 5-335972; corresponding U.S. Pat. No. 5,509,021).
FIG. 11 shows a trellis encoder that generates the trellis-coded modulated signal to be decoded by the above conventional decoder. FIG. 12 is a trellis diagram for the trellis encoder in FIG. 11. The trellis encoder in FIG. 11 has an encoding rate of xc2xe with one noncoding bit and a constraint length of 4. Therefore, this trellis encoder has 2(4xe2x88x921)=8 states that are represented by values of registers D2, D1, and D0 of the encoder, that is, {000}, {001}, {010}, {011}, {100}, {101}, {110}, and {111}. In addition, the values of outputs {y2, y1, y0} of the encoder constitute a subset, and the value of this bit string as binary notation is herein defined as the number of this subset. For example, if {y2, y1, y0}={1, 0, 1}, the subset number is xe2x80x9c5xe2x80x9d, and this subset is referred to as xe2x80x9csubset s5xe2x80x9d. Such subsets s0 through s7 are called subsets A through H in the aforementioned prior art.
The operation of the Viterbi decoder in FIG. 13 is as follows.
A branch metric generator 601 determines Euclidean distances between a reception signal point and respective transmission symbol points, and outputs the results as branch metrics xe2x80x9cBMsxe2x80x9d (xe2x80x9csxe2x80x9d denotes any of the subset numbers 0 to 7). One subset includes two transmission symbol candidates. A branch metric corresponding to the transmission symbol string of which the noncoding bit is xe2x80x9c0xe2x80x9d is denoted by BMs0, while a branch metric corresponding to the transmission symbol string of which the noncoding bit is xe2x80x9c1xe2x80x9d is denoted by BMs1.
A subset maximum likelihood estimator 602 selects one of the two transmission symbol candidates of each subset that has a smaller Euclidean distance, and outputs the selected one as the branch metric BMs for the subset concerned.
A noncoding bit detector 603 extracts the noncoding bit in each selected transmission symbol candidate based on the selection information output from the subset maximum likelihood estimator 602, and outputs the extracted noncoding bit. The noncoding bits are then delayed by j-level shift registers 604 by j levels that correspond to the number of delay levels in a path memory circuit 607.
An add-compare-select (ACS) circuit 605 adds the branch metrics output from the subset maximum likelihood estimator 602 to path metrics of survivor paths in each state at time txe2x88x921, that is, in a state before transition to a state at time t in the trellis diagram shown in FIG. 12. The ACS circuit 605 then selects one of the added values that has the highest likelihood as a path metric PM0 to PM7 of the survivor path. Simultaneously, the selection information is output as a select signal PS0 to PS7.
FIG. 14 is a block diagram of a basic unit of the ACS circuit. For simplifying the description, FIG. 14 illustrates only a basic unit corresponding to state i. In the case of the above conventional decoder, since the number of states is 8, a total of eight basic units with the configuration shown in FIG. 14 are arranged in parallel in the ACS circuit 605.
Adders 700a to 700d receive path metrics PMa to PMd and branch metrics BMa to BMd in accordance with the trellis diagram shown in FIG. 12. The respective added results a to d are input into a comparator 701. The comparator 701 compares the added results a to d, selects one having the highest likelihood, and outputs a select signal PSi representing the selected result. Specifically, if the added result a is selected, xe2x80x9c0xe2x80x9d is output. Likewise, if the added results b, c, and d are selected, xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, and xe2x80x9c3xe2x80x9d are output, respectively. A selector 702 receives the added results a to d and the select signal PSi, and outputs to a register 703 one of the added results that corresponds to the select signal PSi as a new path metric PMi for state i.
The order of {(PMa,BMa), (PMb,BMb), (PMc,BMc), (PMd,BMd)} input into the basic unit is set as follows for the respective states in the above conventional decoder.
 less than State 0 greater than 
{(PM0,BM0), (PM2,BM4), (PM4,BM2), (PM6,BM6)}
 less than State 1 greater than 
{(PM0,BM4), (PM2,BM0), (PM4,BM6), (PM6,BM2)}
 less than State 2 greater than 
{(PM0,BM2), (PM2,BM6), (PM4,BM0), (PM6,BM4)}
 less than State 3 greater than 
{(PM0,BM6), (PM2,BM2), (PM4,BM4), (PM6,BM0)}
 less than State 4 greater than 
{(PM1,BM1), (PM3,BM5), (PM5,BM3), (PM7,BM7)}
 less than State 5 greater than 
{(PM1,BM5), (PM3,BM1), (PM5,BM7), (PM7,BM3)}
 less than State 6 greater than 
{(PM1,BM3), (PM3,BM7), (PM5,BM1), (PM7,BM5)}
 less than State 7 greater than 
{(PM1,BM7), (PM3,BM3), (PM5,BM5), (PM7,BM1)}
The path select signals PS0 to PS7 output from the ACS circuit 605 are input into the path memory 607. FIG. 15 illustrates the path memory 607, which is basically configured to concretize the transitions to respective nodes in the trellis diagram. Registers disposed at positions corresponding to the nodes store values selected among those output from the immediately preceding registers in accordance with the respective path select signals PS0 to PS7.
At the first level, the subset number itself is selected by the path select signal PSi. Accordingly, the subset numbers at each branch in the trellis diagram in FIG. 12 are input into a selector 800. For example, in state 0, when the path select signal PS0 is xe2x80x9c0xe2x80x9d, (PM0,BM0) has been selected. Therefore, the selector 800 outputs the subset number xe2x80x9c0xe2x80x9d, which is stored in a register 801. Likewise, when the path select signal PS0 is xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, and xe2x80x9c3xe2x80x9d, the selector 800 outputs the subset number xe2x80x9c4xe2x80x9d, xe2x80x9c2xe2x80x9d, and xe2x80x9c6xe2x80x9d, respectively. In states 1 to 7, also, the selector 800 outputs a subset number x corresponding to each of the path select signals PS1 to PS7. The output results are stored in the respective registers 801.
At the second level, a value stored in a register corresponding to the node number at the first level is selected. For example, in state 0, when the path select signal PS0 is xe2x80x9c0xe2x80x9d, (PM0,BM0) has been selected. Therefore, a selector 802 outputs the content of the register corresponding to state 0 at the first level, which is then stored in a register 803. Likewise, when the path select signal PS0 is xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, and xe2x80x9c3xe2x80x9d, the selector 802 outputs the content of register 2, 4, and 6, respectively. In states 1 to 7, also, the selector 802 outputs the content of register x at the first level corresponding to the state number x represented by the value of each of the path select signals PS1 to PS7. The output results are stored in the respective registers 803.
The above configuration at the second level is repeated for the third and subsequent levels until the j-th level. In this way, values are shifted from the first level through the j-th level for j clocks. Thus, a value stored in register n at the j-th level is equal to the subset number in the state through which the survivor path in state n has passed j time points earlier. The outputs from the registers at the j-th level are input into a selector 608.
A most likely path decision circuit 606 receives the outputs PM0 to PM7 from the registers of the respective basic units of the ACS circuit 605, detects the state having the highest likelihood among the inputs, and outputs the number of the detected state. Selector 608 receives the output of the most likely path decision circuit 606 and selects the corresponding register output value. The register output value is equal to the subset number that will be obtained by going back along the most likely path by j levels. In the case of the encoder shown in FIG. 11, the two higher-order bits of the subset number are equal to the bits of input information. Accordingly, the two higher-order bits of the subset number output from the selector 608 represent decoded coding bits (x2,x1). Further, based on the decoded subset number output from the selector 608, a selector 609 selects a noncoding bit x3 delayed by j levels for the subset number. The noncoding bit x3 in combination with the coding bits (x2,x1) are output as the decoding results of the Viterbi decoder.
The above conventional configuration has the following problems.
First, used conventionally as the path memory is the configuration as shown in FIG. 15 composed of combinations of selectors and registers, just concretizing the trellis diagram. Accordingly, if the truncation length (j levels in this case) increases or the number of states in the encoder increases, the circuit size of the path memory markedly increases. This results in significant increase in the circuit area of the entire device and power consumption.
Secondly, in the path memory as shown in FIG. 15, connections to the respective selectors are unique to a specific encoder. It is therefore difficult to configure a general-purpose decoder usable for different encoders.
Thirdly, the path memory conventionally stores subset numbers themselves. With this configuration, when the encoding rate of a trellis encoder is reduced by increasing the number of bits of a code from 3 to 4 or even 5, for example, the number of bits of each subset number increases thereby increasing the number of bits stored in the path memory. This also results in increase in the circuit area of the entire device.
Objects of the present invention are providing a Viterbi decoder and a Viterbi decoding method for decoding a trellis-coded modulated signal, where a path memory is configured of a general RAM thereby reducing the circuit size and power consumption.
Specifically, the present invention provides a Viterbi decoder for decoding a trellis-coded modulated signal including: a subset selector section for receiving a reception signal, selecting a transmission symbol having the highest likelihood with respect to a reception symbol point for each subset, and outputting a branch metric corresponding to the selected transmission symbol and a subset select signal for specifying the selected transmission symbol; delays for delaying the subset select signals for a predetermined time; an add-compare-select (ACS) section for receiving the branch metrics, performing arithmetic operation to obtain path metrics in accordance with a trellis diagram, and outputting path select signals for selecting paths having high likelihood; a trace-back memory for storing the path select signals; a trace-back section for tracing back the path select signals stored in the trace-back memory by a predetermined trace-back length from a start node number as a start point; a subset number generator section for outputting, using the number of a first node through which a most likely path passes obtained by the trace-back section and in accordance with a trellis diagram, coding bits relating to transition to the first node and a subset number; and a selector section for receiving the subset number and the subset select signals output from the delays and outputting a noncoding bit relating to the transition to the first node, wherein the coding bits output from the subset number generator section and the noncoding bit output from the selector section are combined to produce a decoded signal.
The subset number generator section preferably generates the coding bits and the subset number using the first node number and a second node number through which the most likely path has passed one time point before the first node.
Alternatively, the subset number generator section preferably generates the coding bits and the subset number using the first node number and a path select signal corresponding to the first node.
According to another aspect of the invention, a Viterbi decoding method for decoding a trellis-coded modulated signal is provided. The method includes the steps of: selecting a transmission symbol having the highest likelihood with respect to a reception symbol point for each subset based on a reception signal, to generate a branch metric corresponding to the selected transmission symbol and a subset select signal for specifying the selected transmission symbol; delaying the subset select signals for a predetermined time; performing add-compare-select (ACS) operation including receiving the branch metrics, performing arithmetic operation to obtain path metrics in accordance with a trellis diagram, and out-putting path select signals for selecting paths having high likelihood; storing the path select signals in a trace-back memory; tracing back the path select signals stored in the trace-back memory by a predetermined trace-back length from a start node number as a start point; generating, using the number of a first node through which a most likely path passes obtained by the tracing back and in accordance with a trellis diagram, coding bits relating to transition to the first node and a subset number; and selecting a noncoding bit relating to the transition to the first node based on the subset number and the delayed subset select signals, wherein the coding bits and the noncoding bit are combined to produce a decoded signal.